package leetcode_题库;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : DingPerferences->Appearance
 * @create 2022/8/19 11:11
 */
public class _1_两数之和 {
    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 4};
        int target = 6;
        
        System.err.println(Arrays.toString(getArray(nums, target)));
    }


    private static int[] getArray(int[] nums, int target) {
        //第一种解法，是最大复杂度的双指针解法，即类似于冒泡排序的比较法，但时间效率很差：
        /*
            > 2022/08/19 14:18:53
            解答成功:
                执行耗时:50 ms,击败了30.65% 的Java用户
                内存消耗:41.7 MB,击败了37.50% 的Java用户
         */

        //我们可以用哈希表来解决问题，键记录当前元素的值，值记录当前元素角标
        //第一次一定是put，从第二次开始，比较，若key中存在target-nums[i]的结果，其实就是key + nums[i] = target。
        //那么，i和第target-nums[i]这个key对应的value就是达成条件的两个角标。顺序当然是map中小，因为是按序put的

        /*
           > 2022/08/19 14:35:17
            解答成功:
                执行耗时:1 ms,击败了99.56% 的Java用户
                内存消耗:41.6 MB,击败了51.70% 的Java用户
         */
        //创建hash表
        Map<Integer,Integer> map = new HashMap<>();
        //遍历
        for (int i = 0;i<nums.length;i++) {
            //如果存在一个key满足条件
            if (map.containsKey(target - nums[i])){
                //返回目标key的val（它的角标）和i（当前角标）即可
                return new int[]{map.get(target - nums[i]),i};
            }
            //继续记录第i个元素的key和val，记录nums[i]是为了寻找key，而记录i是为了返回角标
            map.put(nums[i],i);
        }
        return new int[0];
    }
}
